package LeetCode.exercise;

public class LC309 {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] dp1 = new int[n], dp2 = new int[n], dp3 = new int[n];
        // dp1[i] 表示到第 i 天后，股票已买入（可卖出）时的最大利润
        // dp2[i] 表示到第 i 天后，股票可买入（未买）时的最大利润
        // dp3[i] 表示到第 i 天后，股票不可买入时（冷冻期）的最大利润
        dp1[0] = -prices[0];
        for(int i = 1; i < n; i++){
            dp1[i] = Math.max(dp1[i-1], dp2[i-1]-prices[i]);
            dp2[i] = Math.max(dp2[i-1], dp3[i-1]);
            dp3[i] = dp1[i-1] + prices[i];
        }
        return Math.max(dp2[n-1], dp3[n-1]);
    }
}
